package SeqGraph;

import java.util.Scanner;

import Graph.Graph;
import Graph.GraphKind;


public class MatrixGraph extends Graph {
    public MatrixGraph() {
        Scanner sc = new Scanner(System.in);
        System.out.println("输入图的类型");
        kind = kind.valueOf();
        createGraph(kind, 0, null, null);
        sc.close();
    }

    public MatrixGraph(GraphKind kind, int arcNum, Object[] vexs, int[][] arcs) {
        super(kind, arcNum, vexs, arcs);
        createGraph(kind, arcNum, vexs, arcs);
    }




    /**
     * 创建图:通过输入
     */
    public void createGraph() {
        Scanner sc = new Scanner(System.in);
        System.out.println("输入图的类型");
        kind = kind.valueOf();
        System.out.println("输入图的顶点数量,边的数量:");
        vexNum = sc.nextInt();
        arcNum = sc.nextInt();
        // 图的顶点数组
        vexs = new Object[vexNum];
        // 初始化顶点数组的值
        for (int i = 0; i < vexNum; i++) {
            vexs[i] = sc.next();   // 顶点值
        }
        // 初始化邻接矩阵
        for (int i = 0; i < vexNum; i++) {
            for (int j = 0; j < vexNum; j++) {
                arcs[i][j] = INFINITY;
            }
        }
        sc.close();

        switch (kind) {
            case UDN:
                createUDN(); // 构建无向网
                break;
        }
    }

    private void createUDG() {
    }


    private void createGraph(GraphKind graphKind, int arcNum, Object[] vexs, int[][] arcs) {
        // 填充顶点表
        for (int i = 0; i < vexs.length; i++) {
            this.vexs[i] = vexs[i];
        }
        // 初始化邻接矩阵(含网)
        for (int i = 0; i < vexNum; i++) {
            for (int j = 0; j < vexNum; j++) {
                this.arcs[i][j] = INFINITY;
            }
        }

        switch (graphKind) {
            case UDN:
                createUDN(arcs); // 构建无向图
                break;
        }
    }

    /**
     * 构建无向图:输入
     */
    private void createUDN() {
        Scanner sc = new Scanner(System.in);
        // 通过邻接矩阵建立顶点之间关系
        for (int i = 0; i < arcNum; i++) {
            // 按照2个顶点一条边的方式建立
            int v = locateVex(sc.next());
            int u = locateVex(sc.next());
            // 边的值
            arcs[v][u] = arcs[u][v] = sc.nextInt();
        }
        sc.close();
    }

    /**
     * 构建无向图:按二维数组
     */
    private void createUDN(int[][] arcs) {
        for (int i = 0; i < vexNum; i++) {
            for (int j = 0; j < vexNum; j++) {
                if (arcs[i][j] != 0) {
                    this.arcs[i][j] = arcs[i][j];
                }
            }
        }
    }

    /**
     * 显示所有顶点
     */
    public void showVexs() {
        for (int i = 0; i < vexs.length; i++) {
            System.out.print(vexs[i].toString());
            if (i != vexNum - 1) {
                System.out.print(" , ");
            }
        }
        System.out.println();
    }

    @Override
    public void showArcs() {
    }

    @Override
    public int getVexNum() {
        return vexNum;
    }

    @Override
    public int getArcNum() {
        return arcNum;
    }

    @Override
    public Object getVex(int v) {
        if (v < 0 || v >= vexNum) {
            System.out.println("这个邻接点不存在");
            return null;
        }

        return this.vexs[v];
    }

    /**
     * 根据顶点的值,给出其在顶点数组中的位置
     *
     * @param vex 顶点结点
     * @return 当前顶点在顶点存储集合中的index
     */
    @Override
    public int locateVex(Object vex) {
        for (int i = 0; i < vexNum; i++) {
            if (vexs[i].equals(vex)) {
                return i;
            }
        }
        return -1;
    }


    public int firstAdjVex(int v) {
        if (v < 0 || v >= vexNum) {
            System.out.println("不存在第" + v + "个邻接点");
            return -1;
        }

        for (int j = 0; j < vexNum; j++) {
            if (arcs[v][j] != 0 && arcs[v][j] < INFINITY) {
                return j;
            }
        }

        return -1;
    }


    public int nextAdjVex(int v, int w) {
        if (v < 0 || v >= vexNum) {
            System.out.println("不存在第" + v + "个邻接点");
            return -1;
        }

        // 从第v行的w+1列开始查找
        for (int j = w + 1; j < vexNum; j++) {
            if (arcs[v][j] != 0 && arcs[v][j] < INFINITY) {
                return j;
            }
        }
        return -1;
    }

    public void dfs(int v) {
        if (!visited[v]) {
            visited[v] = true;
            dfsList.add(vexs[v]);
        }
        // 遍历邻接矩阵中的第v行
        for (int j = 0; j < this.vexNum; j++) {
            // 满足2个条件:
            // (1)是否邻接 (2)是否访问过
            if (this.arcs[v][j] != 0 && this.arcs[v][j] < INFINITY && !visited[j]) {
                System.out.println(this.arcs[v][j]);
                dfs(j);
            }
        }
    }

    protected void bfs(int v) {
        // 没有访问过则入队
        if (!visited[v]) {
            visited[v] = true;
            queue.offer(v);
        }
        // 遍历顶点v所在行,检查是否访问过
        for (int j = 0; j < vexNum; j++) {
            // 没有访问过则入队
            if (this.arcs[v][j] != 0 && this.arcs[v][j] < INFINITY && !visited[j]) {
                visited[j] = true;
                queue.offer(j);
            }
        }
        // 遍历第i行结束后, 出队, 且遍历当前队头所在行
        if (!queue.isEmpty()) {
            int vex = (int) queue.poll();
            bfsList.add(getVex(vex));
            if (!queue.isEmpty()) {
                bfs((int) queue.peek());
            }
        }
    }
}